#include <bits/stdc++.h>
using namespace std;

/*
2683. 相邻值的按位异或
已解答
中等
相关标签
premium lock icon
相关企业
提示
下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或（⊕）派生而来。

特别地，对于范围 [0, n - 1] 内的每个下标 i ：

如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
否则 derived[i] = original[i] ⊕ original[i + 1]
给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。

如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。

二进制数组是仅由 0 和 1 组成的数组。
 

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0
示例 2：

输入：derived = [1,1]
输出：true
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1
示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。
 

提示：

n == derived.length
1 <= n <= 105
derived 中的值不是 0 就是 1 。
*/

// 法一
class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        // 初始化
        int ans = 0;
        // 遍历计算派生数组计算异或和
        for (int x : derived) ans ^= x;

        // 所有元素异或和必须为0 原始数组环形 抵消了
        return ans == 0;
    }
};

// 法二 
/// >= C++17
class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        // 核心逻辑：计算派生数组所有元素的异或和
        // - std::reduce 对 derived 数组元素执行累积异或操作
        // - derived.begin(), derived.end(): 遍历整个派生数组
        // - 0: 初始值（异或运算的单位元，不影响结果）
        // - std::bit_xor<>(): 二元操作函数，执行按位异或运算[3,6](@ref)
        int totalXor = std::reduce(derived.begin(), derived.end(), 0, std::bit_xor<>());

        // 关键数学原理：
        // 设原始数组为 original[0..n-1]，派生数组满足：
        //   derived[i] = original[i] XOR original[(i+1)%n]
        // 将派生数组所有元素异或：
        //   totalXor = (original[0]⊕original[1]) ⊕ (original[1]⊕original[2]) ⊕ ... ⊕ (original[n-1]⊕original[0])
        // 由于异或满足结合律和交换律：(a⊕b)⊕(b⊕c) = a⊕(b⊕b)⊕c = a⊕0⊕c = a⊕c
        // 最终相同元素成对抵消（如 original[1] 出现两次），得：
        //   totalXor = original[0]⊕original[0] ⊕ ... = 0[7,9](@ref)
        // 因此当且仅当异或和为0时，存在有效原始数组
        
        // 返回异或和是否为0（若为0则存在原始数组）
        return !totalXor;  // totalXor==0 时返回 true，否则 false
    }
};